/**
 * 1277. 统计全为 1 的正方形子矩阵
 * https://leetcode-cn.com/problems/count-square-submatrices-with-all-ones/
 */
public class Solutions_1277 {
    public static void main(String[] args) {
//        int[][] matrix = {{0, 1, 1, 1},
//                          {1, 1, 1, 1},
//                          {0, 1, 1, 1}};  // output: 15
//        解释：
//        边长为 1 的正方形有 10 个。
//        边长为 2 的正方形有 4 个。
//        边长为 3 的正方形有 1 个。

        int[][] matrix = {{1, 0, 1},
                          {1, 1, 0},
                          {1, 1, 0}};  // output: 7

        int result = countSquares(matrix);
        System.out.println(result);
    }

    /**
     * 解题思路：动态规划
     * dp[i][j] = 2，表示以 [i, j] 为右下角的正方形的数量有 2 个，而面积大小为 1 和 2
     *
     */
    public static int countSquares(int[][] matrix) {
        int res = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (matrix[i][j] == 0) {
                    continue;
                }
                if (i > 0 && j > 0) {
                    // 以 [i, j] 为正方形右下角时，可能构成面积大于 1 的正方形
                    // 以 [i, j] 为正方形右下角时，构成的正方形面积取决于左上角、上边、左边的最小值
                    matrix[i][j] = Math.min(matrix[i - 1][j - 1],
                            Math.min(matrix[i][j - 1], matrix[i - 1][j])) + 1;
                }
                res += matrix[i][j];
            }
        }
        return res;
    }
}
